package com.yuan.algorithms.arithmetic_2;

class IntPair {
	int min;
	int max;
	
	private IntPair min_max(int[] a, int low, int high) {
		IntPair pair = new IntPair();
		
		if (low>high-2) {
			if (a[low]<a[high]) {
				pair.min = a[low];
				pair.max = a[high];
			}else {
				pair.max = a[low];
				pair.min = a[high];
			}
		}else {
			int mid = (low + high)/2;
			IntPair p1 = min_max(a, low, mid);//递归前半部分数据，求解局部最大与最小值
			IntPair p2 = min_max(a, mid+1, high);//递归求解后半部分
			
			pair.min = p1.min < p2.min ? p1.min : p2.min;
			pair.max = p1.max > p2.max ? p1.max : p2.max;
		}
		return pair;
	}
	
	/**
	 * 返回数组中的最大值与最小值
	 * @param arr
	 * @return
	 */
	public IntPair Min_Max(int[] arr) {
		return min_max(arr, 0, arr.length-1);
	}
}
public class 分治_求最大值与最小值 {

	public static void main(String[] args) {
		int[] test = {5,1,23,43,5,34,23,2,4,657,768,567,345,78,45,43,2,5,0,45,345,234,2,4345,67,435,24,45,6,489,4,654,87,8,-9,49,49,78,-48,-464,7987};
		int[] a = {3,12,5,7,-214};
		IntPair ip = new IntPair();
		ip = ip.Min_Max(a);
		System.out.println("min:"+ip.min+"  max:"+ip.max);
	}

}

